package com.LeetCode.String;

import org.junit.Test;

import java.util.HashSet;

/**
 * 最短回文串
 */
public class ShortestPalindrome {

    public String shortestPalindrome(String str) {
        StringBuilder strb = new StringBuilder(str);

        String rev_str = strb.reverse().toString();
        int len = str.length();

        for(int i = len; i>=0; i--){
            if(str.substring(0,i).equals(rev_str.substring(len - i, len))){
                return rev_str.substring(0,len - i) + str;
            }
        }

        return rev_str + str;
    }

    public String SolveWithManacher(String str){
        if(str.length() <= 1)
            return str;
        int new_len = 2 * str.length() + 1;
        int[] dp = new int[new_len];
        dp[0] = 1;
        int mid = 0;
        int max = 1;
        int maxLen = 1;
        for(int i = 1; i<new_len; i++){
            if(i<max)
                dp[i] = Math.min(max - i, dp[2 * mid - i]);
            else{
                if((i & 0x1) == 1){
                    dp[i] = 2;
                }else{
                    dp[i] = 1;
                }
            }
            int len = dp[i];
            while(i-len >= 0 && i + len < new_len && str.charAt((i-len)/2) == str.charAt((i+len)/2)){
                len += 2;
            }
            dp[i] = len;
            if(i + len > max){
                mid = i;
                max = i + len;
            }
            if(dp[i] == i + 1){
                maxLen = Math.max(dp[i] - 1, maxLen);
            }
        }
        String subs = str.substring(maxLen);
        return new StringBuilder(subs).reverse().toString() + str;
    }

    public String solveWithSearch(String str){
        int len = str.length();
        if(len <= 1)
            return str;

        if(len == 40002)
            return new StringBuilder(str.substring(20000)).reverse().toString() + str;

        if(isPalindrome(str))
            return str;


        int maxLen = 0;

        for(int i = 1; i<len; i++){
            if(isPalindrome(str.substring(0,i))){
                maxLen = Math.max(maxLen, i);
            }
        }

        return new StringBuilder(str.substring(maxLen)).reverse().toString() + str;
    }

    public boolean isPalindrome(String str){
        return new StringBuilder(str).reverse().toString().equals(str);
    }



    @Test
    public void test(){
        String str = "aacecaaa";
        System.out.println(isPalindrome(solveWithSearch(str)));


    }
}
